package item40;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * @author Lv Jing
 * @date 2018年08月07日 0:35
 */
public class GetLeastNumbers {

    /**
     * 面试题40：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
     * 思路：典型的topk问题，可以使用局部淘汰法配合最大堆可以找到最终的k个最小数。首先建立一个k大小的数组容器，然后重建为最大堆，
     * 随后遍历数组剩余元素，依次与最大堆的堆顶比较。
     */
    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<>();
            if (input == null || input.length <= 0 || k > input.length) {
                return list;
            }

            // 让数组的前k个数构成最大堆
            buildMaxHeap(input, k - 1);

            // 依次遍历第k+1个数，与最大堆堆顶的数比较
            for (int i = k; i < input.length; i++) {
                if (input[i] < input[0]) {
                    swap(input, i, 0);
                    buildMaxHeap(input, k - 1);
                }
            }

            for (int i = 0; i < k; i++) {
                list.add(input[i]);
            }
            return list;
        }

        private void buildMaxHeap(int[] input, int lastPos) {
            for (int pos = (lastPos-1)/2; pos >= 0; pos--) {
                // 左节点存在
                while (pos *2 + 1 <= lastPos) {
                    int biggerPos = pos *2 + 1;
                    if (biggerPos < lastPos) {
                        if (input[biggerPos] < input[biggerPos+1]) {
                            biggerPos++;
                        }
                    }

                    if (input[pos] < input[biggerPos]) {
                        swap(input, pos, biggerPos);
                    } else {
                        break;
                    }
                }
            }
        }

        private void swap(int[] input, int i, int j) {
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    }

    @Test
    public void test01() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = random.nextInt(100);
        }
        Solution solution = new Solution();
        System.out.println(Arrays.toString(arr));
        System.out.println(solution.GetLeastNumbers_Solution(arr, 3));
    }
}
